1. Field of the Invention
The present invention relates to a method, system, and article of manufacture for generating a value associated with one of a plurality of leaf nodes by implicitly randomly climbing an implicit tree having the leaf nodes.
2. Description of the Related Art
As part of benchmark testing process of storage devices, realistic access patterns of storage locations, such as tracks, blocks, etc., of the storage device must be generated so that Input/Output (I/O) requests may be directed to the randomly generated storage locations according to a realistic access pattern. In this way, the testing process generates test I/O requests in a realistic access pattern to storage locations in the storage device. The prior art technique for randomly generating storage locations to use in the benchmark testing assumes that the number of storage locations of storage being accessed is a power of two.
To select a storage location of the power of two number of storage locations, the testing process models the number of storage locations as the leaves of a binary tree of height H_max. The ancestors of any given track number 0<=v<=2H—max−1 are identified implicitly by the binary representation of the number v. For example, suppose that H_max=3. Then any of the eight available track numbers v can be represented as a three-digit binary number. The parent of any track v, in turn, can be represented as a two digit binary number, obtained by dropping the last binary digit of the number v; the grandparent can be represented as a one digit binary number, obtained by dropping the last two binary digits of the number v; and all tracks have the same great-grandparent.
Starting from a given leaf vi of the tree, the next leaf vi+1 is determined as follows. First, climb a number of nodes 0<=k<<H_max above leaf vi. Then, with probability C, climb one node higher; with another probability of C, climb an additional node higher; and so on (but stop at the top of the tree). Finally, select a leaf at random from all of those belonging to the subtree under the current node. This technique of calculating a leaf node by implicitly randomly climbing a binary tree is further described in U.S. Pat. No. 5,930,497.
There is a need in the art for improved techniques for generating a random number by implicitly random walking up a tree when the tree is not limited to a number of leaves that are a power of two.